<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Introduction
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial086.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial088.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc160">12.1</A>&nbsp;&nbsp;Introduction</H2><UL>
<LI><A HREF="tutorial087.html#toc75">Overview of Search Methods</A>
<LI><A HREF="tutorial087.html#toc76">Optimisation and Search</A>
<LI><A HREF="tutorial087.html#toc77">Heuristics</A>
</UL>

In this chapter we will take a closer look at the principles and
<A NAME="@default297"></A>
alternative methods of searching for solutions in the presence of
constraints. Let us first recall what we are talking about.
We assume we have the standard pattern of a constraint program:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
solve(Data) :-
        model(Data, Variables),
        search(Variables),
        print_solution(Variables).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
The model part contains the logical <EM>model</EM> of our problem. It defines
the variables and the constraints.
Every variable has a <EM>domain</EM> of values that it can take
(in this context, we only consider domains with a finite number of values).<BR>
<BR>
Once the model is set up, we go into the search phase.
Search is necessary since generally the implementation of the constraints
is not complete, i.e. not strong enough to logically infer directly
the solution to the problem. Also, there may be multiple solutions
which have to be located by search, e.g. in order to find the best one.
In the following, we will use the following terminology:
<UL CLASS="itemize"><LI CLASS="li-itemize">
If a variable is given a value (from its domain, of course),
 <A NAME="@default298"></A>
 we call this an <EM>assignment</EM>. If every problem variable is given
 a value, we call this a <EM>total assignment</EM>.
<LI CLASS="li-itemize">A total assignment is a <EM>solution</EM> if it satisfies all the
 constraints.
<LI CLASS="li-itemize">The <EM>search space</EM> is the set of all possible total assignments.
 <A NAME="@default299"></A>
 The search space is usually very large because it grows exponentially
 with the problem size:
 <DIV CLASS="center">
 <I>SearchSpaceSize</I> = <I>DomainSize</I><SUP><I>NumberOfVariables</I></SUP>
 </DIV>
</UL>
<A NAME="toc75"></A>
<H3 CLASS="subsection"><A NAME="htoc161">12.1.1</A>&nbsp;&nbsp;Overview of Search Methods</H3>

<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
<DIV CLASS="center">
<IMG SRC="tutorial032.gif">
</DIV>
<BR>
<BR>
<DIV CLASS="center">Figure 12.1: A search space of size 16</DIV><BR>
<BR>

<A NAME="figsearchspace"></A>
<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
Figure <A HREF="#figsearchspace">12.1</A> shows a search space with N (here 16)
possible total assignments, some of which are solutions.
Search methods now differ in the way in which these assignments
are visited.
We can classify search methods according to different criteria:
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>Complete vs incomplete exploration</B><DD CLASS="dd-description"> complete search means that the search space
 <A NAME="@default300"></A>
 <A NAME="@default301"></A>
 is investigated in such a way that all solutions are guaranteed to be found.
 This is necessary when the optimal solution is needed (one has to prove
 that no better solution exists). Incomplete search may be sufficient when
 just some solution or a relatively good solution is needed.
<DT CLASS="dt-description"><B>Constructive vs move-based</B><DD CLASS="dd-description"> this indicates whether the method advances
 <A NAME="@default302"></A>
 <A NAME="@default303"></A>
 by incrementally constructing assignments (thereby reasoning about partial
 assignments which represent subsets of the search space) or by moving
 between total assignments (usually by modifying previously explored
 assignments).
<DT CLASS="dt-description"><B>Randomness</B><DD CLASS="dd-description"> some methods have a random element while others follow
 <A NAME="@default304"></A>
 fixed rules.
</DL>
Here is a selection of search methods together with their properties:<BR>
<BR>
<DIV CLASS="center">
<TABLE BORDER=1 CELLSPACING=0 CELLPADDING=1>
<TR><TD ALIGN=left NOWRAP>Method</TD>
<TD ALIGN=left NOWRAP>exploration</TD>
<TD ALIGN=left NOWRAP>assignments</TD>
<TD ALIGN=left NOWRAP>random</TD>
</TR>
<TR><TD ALIGN=left NOWRAP>Full tree search</TD>
<TD ALIGN=left NOWRAP>complete</TD>
<TD ALIGN=left NOWRAP>constructive</TD>
<TD ALIGN=left NOWRAP>no</TD>
</TR>
<TR><TD ALIGN=left NOWRAP>Credit search</TD>
<TD ALIGN=left NOWRAP>incomplete</TD>
<TD ALIGN=left NOWRAP>constructive</TD>
<TD ALIGN=left NOWRAP>no</TD>
</TR>
<TR><TD ALIGN=left NOWRAP>Bounded backtrack</TD>
<TD ALIGN=left NOWRAP>incomplete</TD>
<TD ALIGN=left NOWRAP>constructive</TD>
<TD ALIGN=left NOWRAP>no</TD>
</TR>
<TR><TD ALIGN=left NOWRAP>Limited discrepancy</TD>
<TD ALIGN=left NOWRAP>complete</TD>
<TD ALIGN=left NOWRAP>constructive</TD>
<TD ALIGN=left NOWRAP>no</TD>
</TR>
<TR><TD ALIGN=left NOWRAP>Hill climbing</TD>
<TD ALIGN=left NOWRAP>incomplete</TD>
<TD ALIGN=left NOWRAP>move-based</TD>
<TD ALIGN=left NOWRAP>possibly</TD>
</TR>
<TR><TD ALIGN=left NOWRAP>Simulated annealing</TD>
<TD ALIGN=left NOWRAP>incomplete</TD>
<TD ALIGN=left NOWRAP>move-based</TD>
<TD ALIGN=left NOWRAP>yes</TD>
</TR>
<TR><TD ALIGN=left NOWRAP>Tabu search</TD>
<TD ALIGN=left NOWRAP>incomplete</TD>
<TD ALIGN=left NOWRAP>move-based</TD>
<TD ALIGN=left NOWRAP>possibly</TD>
</TR>
<TR><TD ALIGN=left NOWRAP>Weak commitment</TD>
<TD ALIGN=left NOWRAP>complete</TD>
<TD ALIGN=left NOWRAP>hybrid</TD>
<TD ALIGN=left NOWRAP>no</TD>
</TR></TABLE>
</DIV><BR>
<BR>
<A NAME="@default305"></A>
<A NAME="@default306"></A>
The constructive search methods usually organise the search space by
partitioning it systematically. This can be done naturally with a
search tree (Figure <A HREF="#figsearchtree">12.2</A>). The nodes in this tree
represent choices which partition the remaining search space into two
or more (usually disjoint) sub-spaces. Using such
a tree structure, the search space can be traversed systematically and
completely (with as little as O(N) memory requirements).
<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
<DIV CLASS="center">
<IMG SRC="tutorial033.gif">
</DIV>
<BR>
<BR>
<DIV CLASS="center">Figure 12.2: Search space structured using a search tree</DIV><BR>
<BR>

<A NAME="figsearchtree"></A>
<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
Figure <A HREF="#figtreesearch">12.4</A> shows a sample tree search, namely a depth-first
incomplete traversal.
As opposed to that, figure <A HREF="#figmovesearch">12.3</A> shows an example of an
incomplete move-based search which does not follow a fixed search space
structure. Of course, it will have to take other precautions to avoid
looping and ensure termination.
<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
<DIV CLASS="center">
<IMG SRC="tutorial034.gif">
</DIV>
<BR>
<BR>
<DIV CLASS="center">Figure 12.3: A move-based search</DIV><BR>
<BR>

<A NAME="figmovesearch"></A>
<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
<DIV CLASS="center">
<IMG SRC="tutorial035.gif">
</DIV>
<BR>
<BR>
<DIV CLASS="center">Figure 12.4: A tree search (depth-first)</DIV><BR>
<BR>

<A NAME="figtreesearch"></A>
<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
A few further observations:
Move-based methods are usually incomplete. This is not surprising given
typical sizes of search spaces.
A complete exploration of a huge search space
is only possible if large sub-spaces can be excluded a priori, and this
is only possible with constructive methods which allow one to reason about
whole classes of similar assignments.
Moreover, a complete search method must remember which parts of the
search space have already been visited.
This can only be implemented with
acceptable memory requirements if there is a simple structuring of the
space that allows compact encoding of sub-spaces.<BR>
<BR>
<A NAME="toc76"></A>
<H3 CLASS="subsection"><A NAME="htoc162">12.1.2</A>&nbsp;&nbsp;Optimisation and Search</H3>
<A NAME="secbboptsearch"></A>
<A NAME="@default307"></A>
Many practical problems are in fact optimisation problems, ie. we are
not just interested in some solution or all solutions, but in
the best solution.<BR>
<BR>
Fortunately, there is a general method to find the optimal solution
based on the ability to find all solutions.
<A NAME="@default308"></A>
The <EM>branch-and-bound</EM> technique works as follows:
<OL CLASS="enumerate" type=1><LI CLASS="li-enumerate">
Find a first solution
<LI CLASS="li-enumerate">Add a constraint requiring a better solution than the best
 one we have so far (e.g. require lower cost)
<LI CLASS="li-enumerate">Find a solution which satisfies this new constraint.
 If one exists, we have a new best solution and we repeat step 2.
 If not, the last solution found is the proven optimum.
</OL>
The <EM>branch_and_bound</EM> library provides generic predicates 
which implement this technique:
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>minimize(+Goal,-Cost)</B><DD CLASS="dd-description">
This is the simplest predicate in the <EM>branch_and_bound</EM> library:
A solution of the goal <I>Goal</I> is found that minimizes the value of
<EM>Cost</EM>. <EM>Cost</EM> should be a variable that is affected, and 
eventually instantiated, by the execution of <I>Goal</I>. Usually, <I>Goal</I>
is the search procedure of a constraint problem and <I>Cost</I> is the variable
representing the cost.<BR>
<BR>
<DT CLASS="dt-description"><B>bb_min(+Goal, -Cost, ++Options)</B><DD CLASS="dd-description">
A more flexible version where the programmer can take more control
over the branch and bound behaviour and choose between different
strategies and parameter settings.
</DL>
<A NAME="toc77"></A>
<H3 CLASS="subsection"><A NAME="htoc163">12.1.3</A>&nbsp;&nbsp;Heuristics</H3>

Since search space sizes grow exponentially with problem size,
it is not possible to explore all assignments except for the
very smallest problems.
The only way out is <EM>not</EM> to look at the whole search space.
There are only two ways to do this:
<UL CLASS="itemize"><LI CLASS="li-itemize">
<B>Prove</B> that certain areas of the space contain no solutions.
 This can be done with the help of constraints. This is often referred
 to as <EM>pruning</EM><A NAME="@default309"></A>.
<LI CLASS="li-itemize"><B>Ignore</B> parts of the search space that are unlikely to contain
 solutions (i.e. do incomplete search), or at least postpone their exploration.
 This is done by using <EM>heuristics</EM><A NAME="@default310"></A>.
 A heuristic is a particular traversal order of the search space
 which explores promising areas first.
</UL>
In the following sections we will first investigate the considerable
degrees of freedom that are available for heuristics within the framework of
systematic tree search, which is the traditional search method
in the Constraint Logic Programming world.<BR>
<BR>
Subsequently, we will turn our attention to move-based methods
which in ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> can be implemented using the facilities of the 
<TT>repair</TT> library.<BR>
<BR>
<HR>
<A HREF="tutorial086.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial088.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
